The matching of two or more planar point patterns in a computer system is an important technique in the field of computer vision and in the image processing technology. When an image is input into a computer in a digitized format, the "feature points" of the image can be abstracted with the conventional feature abstracting technologies, according to the characters of the image or to the purposes of the processing. The feature points, more concretely, the coordinates and other characters of the points, so obtained can be used in the recognition of the image. For example, by matching the distribution of the feature points of two images patterns, the similarity of the patterns comprising the feature points can be decided. Thus, the similarity of the images can be determined.
A good example of the application of the pattern matching technology is the matching of fingerprints. When the image of a fingerprint is scanned by an image scanner, the image is digitized and input to a computer. The computer uses a software or a circuit to abstract the distribution of the feature points of the fingerprint, usually the end points and the cross points of the lines and curves of the fingerprint. By matching two patterns comprising feature points obtained (scanned) in different time or places, whether the two fingerprints came from the same finger, can be determined.
Another application for the matching technology is the recognition of hand-written characters. Such technology is also called "optical character recognition--OCR" and is especially applicable to the recognition of Chinese characters or Japanese "kanji".
In the matching of two planar point patterns so obtained, several problems will be faced. First, the number of feature points of two patterns could be different, even if they were abstracted from a same image or the same image source. Another problem is, the possibility that each feature point exists at the same position in both patterns can not be forecast. Thirdly, while the images (patterns) were obtained at different time and/or places, the distribution of the feature points in one pattern could be shifted, rotated and/or distorted (enlarged or reduced), in relating to the other pattern.
Taiwan patent application No.79109743 (corresponding to U.S. Pat. No. 5,392,367) related to a "Method and Device for the Automated Matching and Recognition for Planar Pattern Points" wherein a "fuzzy relaxation" approach was introduced.
According to said Taiwan patent, the matching of two planar point patterns are conducted in two steps. The first step is to mate the points of one pattern (the reference pattern) with the points of another pattern (the test pattern). The second step is to calculate the similarity of the two patterns, according to the result of the mating. Here, mating means, for every point (feature point) in the test pattern, locating one only point in the reference pattern, such that the two mated points are overlapped or with very short distance, if they were in the same coordinate system. The reason for the mating includes that, when two patterns are similar, most points of one pattern will be mated with the points of the other.
In the mating process, a "course matching" is used to exclude pairs of points that are impossible to be mated. The initial "mated possibility" of one point from the reference pattern to be mated with one point from the test pattern is set at 0 for those pairs that can not be mated and is set at 1 for other pairs. The mated possibility of a pair is then adjusted by the "fuzzy relaxation" method. In this Taiwan patent, the mated possibility of a pair is adjusted according to "the value of other mated pairs to support such mating, given that such one pair is mated". The mated possibility of one mated pair is adjusted by the following equation: ##EQU1##
wherein S.sup.(r) (pi,qj) represents the mated possibility of points pi and qj, when it is adjusted for the r.sup.th time; pi represents a point from the test pattern P wherein i=1, 2, . . . , m; qj represents a point from the reference pattern Q wherein j=1, 2, . . . , m; Cij(h, k) represents the possibility that another pair ph and qk are mated (ph is a point of Pattern P, h=1, 2, . . . , m, h.noteq.i, qk is a point of Pattern Q, k=1, 2, . . . , m, k.noteq.j) and ##EQU2## l's represent distances between pi and ph or between qj and qk and m represents the least number of points in patterns P and Q.
While the mated possibility of every point from the reference pattern with every point from the test pattern is calculated under the "fuzzy relaxation" method, the best mated pairs, i.e., the pairs with the highest mated possibilities, can be selected under a "sequential forward selection method".
In the second step, the similarity of the reference pattern and the test pattern can be calculated employing the following components. They are: the mated rate (number of mated pairs/least number of points of the two patterns), the average mated possibility, the average distance of mated pairs and the scaling factor.
In order to solve the problem of distortion, including shift, rotation and proportional scaling, a "least mean-square-error" value was introduced to adjust the distribution of the test pattern.
Although the above-said patent taught an automatic matching method for planar point patterns with high efficiency, it inherits the problem of relatively high rejection rate. If the "false acceptance rate--FAR" is set at 0.1%, in matching 800 fingerprint images, its "false rejection rate--FRR" will be about 25%. This means, when two images are from the same fingerprint, the possibility that the system decides they are not from the same fingerprint is 25%.
Nevertheless, the processing under this conventional art takes relatively long time. Matching of two planar point patterns takes approximately 0.45 second in average.
It is then necessary to develop an automatic matching device and method for planar point patterns wherein the FRR can be reduced. It is also necessary to have an automatic matching device and method that match planar point patterns with higher speed.